/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package Administrador;

import java.util.Iterator;
import java.util.logging.Level;
import java.util.logging.Logger;
import structure5.Edge;
import structure5.Graph;
import structure5.GraphMatrixDirected;

/**
 * algoritmo de Floyd
 * @author Vinicio Gomez
 */
public class Floyd {
    /**
     * Algoritmo de Floy
     * @param el grafo a analizar
     * @return un grafo que contiene las aristas de A, B, si existe un camino
     */
    public static GraphMatrixDirected<String, Integer> g;
    private static Graph floyd(Graph<String,Integer> f)
    // post: g contains edge (a,b) if there is a path from a to b
    {
        //COPIAR GRAFO!
        Graph<String,Integer> g = new GraphMatrixDirected<String, Integer>(300);
        g= copiar_grafo(f);
        //g=f;

        Iterator<String> witer = g.iterator();

        while (witer.hasNext())
        {
            Iterator<String> uiter = g.iterator();
            String w = witer.next();
            while (uiter.hasNext())
            {
                Iterator<String> viter = g.iterator();
                String u = uiter.next();
                while (viter.hasNext())
                {
                    String v = viter.next();
                    if (g.containsEdge(u,w) && g.containsEdge(w,v))
                    {
                        Edge<String,Integer> leg1 = g.getEdge(u,w);
                        Edge<String,Integer> leg2 = g.getEdge(w,v);
                        int leg1Dist = leg1.label();
                        int leg2Dist = leg2.label();
                        int newDist = leg1Dist+leg2Dist;

                        if (g.containsEdge(u,v))
                        {
                            Edge<String,Integer> across = g.getEdge(u,v);
                            int acrossDist = across.label();
                            if (newDist < acrossDist) {
                                across.setLabel(newDist);
                            }
                        } else {
                            g.addEdge(u,v,newDist);
                            
                        }
                    }   
                }
            }
        }
        return g;
    }
    
    
    private static int [][] matrixFloyd (GraphMatrixDirected<String,Integer> f){
        GraphMatrixDirected<String, Integer> g = (GraphMatrixDirected<String, Integer>) floyd(f);
        Iterator<String> tmp = g.iterator();
        int len = 1;
        while (tmp.hasNext()){
            tmp.next();
            len++;
        }
        
        int matrix[][] = new int[len][len];
        Iterator<String> witer = g.iterator();
        int columna = 0;
        int fila = 0;

        while (witer.hasNext()) {
            Iterator<String> uiter = g.iterator();
            String w = witer.next();
            while (uiter.hasNext()) {
                String u = uiter.next();
                if (g.containsEdge(u, w)) {
                    Edge leg1 = g.getEdge(u, w);
                    int leg1Dist = (Integer)(leg1.label());
                    //System.out.print(leg1Dist);
                    //int leg1Dist= (Integer)((Edge)(leg1.label())).label();
                    if (fila == columna){
                        matrix[fila][columna] = 0;
                    }
                    else{
                        matrix[fila][columna] = leg1Dist;
                    }
                    
                }
                else{
                    matrix[fila][columna] = 0;
                }
                columna++;
            }
            columna=0;
            fila++;
        }
        return matrix;
    }
    
    /**
     * Imprime la matriz segun el algoritmo de Floyd
     * @param f grafo a imprimir
     */
    public static void imprimir_matriz(GraphMatrixDirected<String,Integer> f){
        int [][] matrix = matrixFloyd(f);
        String ciudad_centro = centro_grafo(matrix, g);
        Iterator<String> witer = g.iterator();
        int columna = 0;
        int fila = 0;
        System.out.print("\t"+"\t");
        while (witer.hasNext()) {
            Iterator<String> uiter = g.iterator();
            String w = witer.next();
            System.out.print(w+"\t");
        }
        System.out.println("");
        Iterator<String> siter = g.iterator();
        for (fila = 0; fila < matrix.length -1; fila++) {
            String w = siter.next();
            System.out.print(w+"\t"+"\t");
            for (columna = 0; columna < matrix[fila].length-1; columna++) {
                System.out.print(matrix[fila][columna]+"\t");
            }
            System.out.println("");
        }
        System.out.println("");
        System.out.println("Centro del Grafo: "+ ciudad_centro);
        System.out.println("");
    }    

    private static Graph<String, Integer> copiar_grafo(Graph<String, Integer> f) {
        g = new GraphMatrixDirected<String, Integer>(300);
        Iterator <String> i = f.iterator();
        //agregar todas las ciudades
        while (i.hasNext()){
            g.add(i.next());
        }
        
        //agregar todas las aristas
        Iterator <String> j = f.iterator();
        while (j.hasNext()){
            Iterator <String> k = f.iterator();
            String next = j.next();
            while (k.hasNext()){
                String next2 = k.next();
                if (f.containsEdge(next, next2)){
                    g.addEdge(next, next2, f.getEdge(next, next2).label());
                }
                if (f.containsEdge(next2, next)){
                    g.addEdge(next2, next, f.getEdge(next2, next).label());
                }
            }
        }
        return g;
    }

    private static String centro_grafo(int[][] matrix, GraphMatrixDirected<String, Integer> g1) {
        int fila = 0;
        int columna = 0;
        int mayor[]=new int[matrix.length];
        for (columna=0 ; columna < matrix.length-1; columna ++){
            for (fila = 0 ; fila < matrix.length-1; fila ++) {
                if (matrix[fila][columna] > mayor[columna]){
                    mayor[columna]=matrix[fila][columna];
                }
            }
        }
        int menor= Integer.MAX_VALUE;
        int numero=0;
        for ( columna = 0 ; columna < mayor.length-1;columna++){
            if (mayor[columna]<menor){
                menor = mayor[columna];
                numero=columna;
            }
        }
        Iterator<String> i = g1.iterator();
        while (numero!=0){
            i.next();
            numero--;
        }
        return i.next();
    }
    
    
}
